package hot100.logos61To70;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author logos
 * date 2025/7/16 12:55
 * @version v1.0
 * @Package hot100.logos61To70
 */
public class logos62 {
    /**
     * 62. N 皇后
     * https://leetcode.cn/problems/n-queens/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        private List<List<String>> ans = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            int limit = (1 << n) - 1;
            dfs(limit, 0, 0, 0, new int[n], n, 0);
            return ans;
        }

        private void dfs(int limit, int col, int left, int right, int[] path, int n, int cur) {
            if (col == limit) {
                List<String> tmp = new ArrayList<>();
                for (int k = 0; k < n; k++) {
                    char[] row = new char[n];
                    Arrays.fill(row, '.');
                    row[path[k]] = 'Q';
                    tmp.add(new String(row));
                }
                ans.add(tmp);
                return;
            }
            int totalLimit = col | left | right;
            int canPut = limit & (~totalLimit);
            while (canPut != 0) {
                int place = canPut & (-canPut);
                canPut ^= place;
                int num = Integer.bitCount(place - 1);
                path[cur] = num;
                dfs(limit, col | place, (left | place) >> 1, (right | place) << 1, path, n, cur + 1);
            }
        }
    }
}
